\section{Observations and Perspectives}
\label{sect:concl}

In this paper, we have revived data partitioning \cite{BoLS09}
on top of BaseX and experimentally demonstrated, in the best case of non-trivial
queries, 4-fold speedup on a 12-core server. In this section, as
concluding remarks, we discuss possible improvement of BaseX in terms of 
partitioning strategies and further perspectives on BaseX.


\subsection{BaseX Extensions Desirable}

Since the implementations of query partitioning is reletively simple and mainly
influenced by the structure of input XML documents as we observed, we mainly
focus on the implementations of data partitioning strategies in this discussion.

Although the client-side implementation generally fell behind the server-side
one in our experiments, it has an advantage that it requires less functionality
of XML database servers. If that performance gap were filled, the client-side
one would be preferable. Since the performance gaps in prefix queries were small
even when their result sizes were more than 1 MB, the difference of cost between
sending prefix results to (local) clients and storing them in a server was
marginal. The dominant factor was the cost of sending prefix results back in the
form of long suffix queries and parsing them on a server.  A promising approach
to reducing this overhead is client-server streaming of the starting nodes of a
suffix query. Since one suffix query is in common applied to many starting
nodes, if the suffix query is given to a server in advance, the server can apply
it successively to incoming starting nodes and stream out results to clients.
With this streaming functionality additionally, the client-side implementation
would perform fast nearly to the server-side one.

There is also room for improvement of the server-side implementation. We store
block-partitioned arrays into an in-memory database as text parts and then
deserialize them to sequences. This is, to the best of our knowledge, the most
efficient way of preserving arrays on top of the current BaseX server, but is
merely a workaround because its serialization/deserialization is redundant. The
most efficient way is obviously to keep XQuery data structures as they are on
top of a server. We consider that it would not necessitate a drastic change of
BaseX. Only demand-driven serialization and new function \Src{deserialize}
suffice for it as follows. When XQuery values are put into a text part of an
in-memory database, they are not serialized immediately but keep their
representations. They will be serialized for a query just before the query tries
to read the text part. If a query applies \Src{deserialize} to the text part, it
returns their original representations in zero cost. It is worth noting that
because in-memory databases in BaseX will never be stored on disks,
demand-driven serialization per se is worth implementing to avoid serialization
into text parts not to be accessed.

\subsection{Further Perspectives}

Both data partitioning and index-based optimizations have worked together well
only with the simple way described in Section~\ref{sect:opt}. Both lie in the
same spectrum in the sense that performance gain is contingent on the statistics
of a given document. In fact, document statistics are known to be useful for
data partitioning (as well as query partitioning)
\cite{Bord10}. Statistics maintained together with indices
in BaseX should therefore be utilized for data partitioning together with
index-based optimizations. If we implement data partitioning into BaseX, a close
integration with both would be naturally feasible. Besides, statistics will be
available even outside BaseX by using \emph{probing} queries that count nodes
hitting at a specific step. The cost of several probing queries in advance to
data partitioning would matter little because simple counting queries are quite
fast on BaseX.  By using node counts, we can avoid the situation of an
insufficient number of prefix query results found in XM1(a). It will be a
lightweight choice in the sense of preserving a black-box use of BaseX.

It is challenging yet promising to extend data partitioning to distributed
databases with BaseX. The top part of a document to be traversed by prefix
queries can be either centralized or replicated. Bottom parts to be traversed by
suffix queries should be distributed as separate XML databases. Because the
whole database forms a simple collection of XML documents, horizontal
fragmentation \cite{kling11:dist_xml} will be well-suited but it can incur
imbalance in size among fragments. Balanced-size cheap fragmentation based on
partial trees \cite{HaMa16} will be promising for the complement to it. Existing
work \cite{DaGK14} on querying large integrated data will be relevant. Hybrid
partitioning \cite{BoLS09}, which is combination of data partitioning and query
partitioning, would become important because query partitioning requires
synchronization only in merging partial results and the number of
synchronizations matters more in distributed databases. Fragmentation-aware
hybrid partitioning is worth investigating. The most challenging part is to
implement integration with existing index-based optimizations so as to take
account of global information, where our idea described in
Section~\ref{sect:opt} will be useful but would not be trivially applicable.

\section{Summary}

First, as concluded in~\cite{BoLS09}, it is not obvious if data or query
partitioning would be beneficial. In our implementations, these are caused by
different factors. For the implementations of data partitioning, we need to
process a prefix query before processing the suffix queries in parallel. This is
a extra cost compared to the original query and the amout of extra time for
processing a prefix query relates to the result size of the prefix query. In
case the result size is large, it takes a lot time, such as DBLP1(a) and
DBLP2(a). While for the implementations of query parititioning, the imbalance of
XML documents have a dramatic influence on the query perfomrance and the
speedup.

Second, BaseX optimizer plays an important role in the reduction of execution
time. In case when BaseX optimizer is available, execution time can be greately
reduced. A very important feature of the optimizer is that it can also be
applied in parallel evaluation. Therefore, it is worth taking the optimizations
to reduce the execute time as long as the partition of subqueries can meet the
conditions of the BaseX optimizer.

Third, the experiment results clearly show that we can achrive speedup up to 4,
which have strongly proved that the partitioning stragegies are available not
only on XML trees but also on XML database engines. However, the availability of
these stragegies is significantly dependent on the implementations and the XML
database engine/processor. Properly combined with the features of the XML
database engine/processor used for implementation, we can achrive significant
performance improvements over the original strategies, such as the server-side
implementation of data partitioning strategy.
